/* Quick sort: partition an array on an element (pivot) such that all elements
 * to the left are smaller and all the elements to the right are greater.
 * Recursively quick sort the two sub arrays, not including the pivot element
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}


void print_arr(int arr[], int n)
{
    int i = 0;

    for (i = 0; i < n; i++)
    {
        printf("%4d ", arr[i]);
    }

    printf("\n");
}


/* Returns a pivot index such that all elements to the left are smaller and all
 * elements to the right are greater than that element */
int partition(int arr[], int n)
{
    int rand_pos = rand()%n;
    int pivot_val;
    int pivot_index = 0;
    int i =0;

    if ( n <= 1)
    {
        return n;
    }

    swap(&arr[rand_pos], &arr[n-1]);
    pivot_val = arr[n-1];

    for (i=0; i < n-1; i++)
    {
        if(arr[i] < pivot_val)
        {
            swap(&arr[i], &arr[pivot_index++]);

        }
    }

    swap(&arr[pivot_index], &arr[n-1]);

    return pivot_index;
}


void quick_sort(int arr[], int n)
{
    int pivot_index = 0;

    if (n <= 1)
    {
        return;
    }

    pivot_index = partition(arr, n);

    if (pivot_index > 0)
    {
        quick_sort(arr, pivot_index);
    }

    if (pivot_index < n-1)
    {
        quick_sort(arr+pivot_index+1, n-pivot_index-1);
    }
}


int main(void)
{
    int arr[] = { 99, 22, 13, 43, 67, 7, 27, 23, 4, 15, 81, 46, 64, 8, 17, 18, 19 };
    int size = sizeof(arr)/sizeof(arr[0]);
    srand(time(NULL));

    print_arr(arr, size);
    quick_sort(arr, size);
    print_arr(arr, size);

    return 0;
}
